'''
https://leetcode.cn/problems/single-number-iii/description/
'''
from typing import List


class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        xor_sum = 0
        for num in nums:
            xor_sum ^= num
        # xor_sum = a ^ b
        # last_1  = a^b 最后一位相等的1
        #           也就是说在这一位上，a和b一定是不等的
        #           根据这一位，可以把数组切成两半
        #           一半包含一个a和出现了两次的其他的， 一半包含一个b和出现了两次的其他的
        last_1 = xor_sum & (-xor_sum)
        a = b = 0
        for num in nums:
            if last_1 & num:
                a ^= num
            else:
                b ^= num
        return [a, b]

nums = [1, 1, 2, 2, 3, 4]
res = Solution().singleNumber(nums)
print(res)